﻿using System;

namespace HeroDream
{
    static class FindUtils
    {
        public static void Test()
        {
            int[] array = new int[] { 1, 2, 31, 40 ,51};
            int v = 61;
            int index = FindUtils.BinarySearchF(array, v,0,array.Length-1);
            if (index >= 0)
            {
                Console.WriteLine("数据" + v + "位于位置" + index + "上");
            }
            else
            {
                Console.WriteLine("未查询到数据" + v);
            }
        }

        /// <summary>
        /// 顺序查找
        /// </summary>
        /// <param name="array"></param>
        /// <param name="value"></param>
        /// <returns></returns>
        public static int Find(int[] array,int value)
        {
            for(int i = 0; i < array.Length; i++)
            {
                if (array[i] == value)
                {
                    return i;
                }
            }
            return -1;
        }

        /// <summary>
        /// 二分查找算法循环实现
        /// 必须是有序的可随机访问的数组类型才能使用二分查找
        /// </summary>
        /// <param name="array">数组</param>
        /// <param name="value">查询的数字</param>
        /// <returns>如果找到，返回数组的下标，否则返回-1</returns>
        /// 
        public static int BinarySearch(int[] array, int value,int left,int right)
        {
            if (left > right)
            {
                return -1;
            }

           while (left <= right)
            { 
                int mid= left + (right - left) / 2;
                if (array[mid] < value)
                {
                    //需要去右边找
                    left = mid+1;


                }else if(array[mid] > value)
                {
               right = mid-1;
                }
                else
                {  
                    return mid;
                }
            }
            return -1;
        }

        /// <summary>
        /// 二分查找的递归实现
        /// </summary>
        /// <param name="array"></param>
        /// <param name="value"></param>
        /// <param name="left"></param>
        /// <param name="right"></param>
        /// <returns></returns>
        public static int BinarySearchF(int[] array, int value, int left, int right)
        {
            if (left > right)
            {
                return -1;
            }

            int mid = left + (right - left) / 2;
            if (array[mid] < value)
            {
                //需要去右边找
                return BinarySearchF(array, value, mid + 1, right);

            }
            else if (array[mid] > value)
            {
                return BinarySearchF(array, value, left, mid - 1);
            }
            else
            {
                return mid;
            }
        }

    }
}
